// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/quic/quic_sent_packet_manager.h"

#include <algorithm>

#include "base/logging.h"
#include "base/stl_util.h"
#include "net/quic/congestion_control/general_loss_algorithm.h"
#include "net/quic/congestion_control/pacing_sender.h"
#include "net/quic/crypto/crypto_protocol.h"
#include "net/quic/proto/cached_network_parameters.pb.h"
#include "net/quic/quic_bug_tracker.h"
#include "net/quic/quic_connection_stats.h"
#include "net/quic/quic_flags.h"
#include "net/quic/quic_utils_chromium.h"

using std::max;
using std::min;
using std::pair;

namespace net {

namespace {
    static const int64_t kDefaultRetransmissionTimeMs = 500;
    static const int64_t kMaxRetransmissionTimeMs = 60000;
    // Maximum number of exponential backoffs used for RTO timeouts.
    static const size_t kMaxRetransmissions = 10;
    // Maximum number of packets retransmitted upon an RTO.
    static const size_t kMaxRetransmissionsOnTimeout = 2;
    // Minimum number of consecutive RTOs before path is considered to be degrading.
    const size_t kMinTimeoutsBeforePathDegrading = 2;

    // Ensure the handshake timer isnt't faster than 10ms.
    // This limits the tenth retransmitted packet to 10s after the initial CHLO.
    static const int64_t kMinHandshakeTimeoutMs = 10;

    // Sends up to two tail loss probes before firing an RTO,
    // per draft RFC draft-dukkipati-tcpm-tcp-loss-probe.
    static const size_t kDefaultMaxTailLossProbes = 2;

    // Number of unpaced packets to send after quiescence.
    static const size_t kInitialUnpacedBurst = 10;

    bool HasCryptoHandshake(const TransmissionInfo& transmission_info)
    {
        DCHECK(!transmission_info.has_crypto_handshake || !transmission_info.retransmittable_frames.empty());
        return transmission_info.has_crypto_handshake;
    }

} // namespace

#define ENDPOINT \
    (perspective_ == Perspective::IS_SERVER ? "Server: " : "Client: ")

QuicSentPacketManager::QuicSentPacketManager(
    Perspective perspective,
    QuicPathId path_id,
    const QuicClock* clock,
    QuicConnectionStats* stats,
    CongestionControlType congestion_control_type,
    LossDetectionType loss_type,
    MultipathDelegateInterface* delegate)
    : unacked_packets_()
    , perspective_(perspective)
    , path_id_(path_id)
    , clock_(clock)
    , stats_(stats)
    , delegate_(delegate)
    , debug_delegate_(nullptr)
    , network_change_visitor_(nullptr)
    , initial_congestion_window_(kInitialCongestionWindow)
    , send_algorithm_(
          SendAlgorithmInterface::Create(clock,
              &rtt_stats_,
              congestion_control_type,
              stats,
              initial_congestion_window_))
    , loss_algorithm_(new GeneralLossAlgorithm(loss_type))
    , n_connection_simulation_(false)
    , receive_buffer_bytes_(kDefaultSocketReceiveBuffer)
    , least_packet_awaited_by_peer_(1)
    , first_rto_transmission_(0)
    , consecutive_rto_count_(0)
    , consecutive_tlp_count_(0)
    , consecutive_crypto_retransmission_count_(0)
    , pending_timer_transmission_count_(0)
    , max_tail_loss_probes_(kDefaultMaxTailLossProbes)
    , enable_half_rtt_tail_loss_probe_(false)
    , using_pacing_(false)
    , use_new_rto_(false)
    , undo_pending_retransmits_(false)
    , largest_newly_acked_(0)
    , largest_mtu_acked_(0)
    , handshake_confirmed_(false)
{
}

QuicSentPacketManager::~QuicSentPacketManager() { }

void QuicSentPacketManager::SetFromConfig(const QuicConfig& config)
{
    if (config.HasReceivedInitialRoundTripTimeUs() && config.ReceivedInitialRoundTripTimeUs() > 0) {
        rtt_stats_.set_initial_rtt_us(
            max(kMinInitialRoundTripTimeUs,
                min(kMaxInitialRoundTripTimeUs,
                    config.ReceivedInitialRoundTripTimeUs())));
    } else if (config.HasInitialRoundTripTimeUsToSend() && config.GetInitialRoundTripTimeUsToSend() > 0) {
        rtt_stats_.set_initial_rtt_us(
            max(kMinInitialRoundTripTimeUs,
                min(kMaxInitialRoundTripTimeUs,
                    config.GetInitialRoundTripTimeUsToSend())));
    }
    // TODO(ianswett): BBR is currently a server only feature.
    if (FLAGS_quic_allow_bbr && config.HasReceivedConnectionOptions() && ContainsQuicTag(config.ReceivedConnectionOptions(), kTBBR)) {
        send_algorithm_.reset(SendAlgorithmInterface::Create(
            clock_, &rtt_stats_, kBBR, stats_, initial_congestion_window_));
    }
    if (config.HasReceivedConnectionOptions() && ContainsQuicTag(config.ReceivedConnectionOptions(), kRENO)) {
        if (ContainsQuicTag(config.ReceivedConnectionOptions(), kBYTE)) {
            send_algorithm_.reset(SendAlgorithmInterface::Create(
                clock_, &rtt_stats_, kRenoBytes, stats_, initial_congestion_window_));
        } else {
            send_algorithm_.reset(SendAlgorithmInterface::Create(
                clock_, &rtt_stats_, kReno, stats_, initial_congestion_window_));
        }
    } else if (config.HasReceivedConnectionOptions() && ContainsQuicTag(config.ReceivedConnectionOptions(), kBYTE)) {
        send_algorithm_.reset(SendAlgorithmInterface::Create(
            clock_, &rtt_stats_, kCubicBytes, stats_, initial_congestion_window_));
    }
    if (!FLAGS_quic_disable_pacing_for_perf_tests) {
        EnablePacing();
    }

    if (config.HasClientSentConnectionOption(k1CON, perspective_)) {
        send_algorithm_->SetNumEmulatedConnections(1);
    }
    if (config.HasClientSentConnectionOption(kNCON, perspective_)) {
        n_connection_simulation_ = true;
    }
    if (config.HasClientSentConnectionOption(kNTLP, perspective_)) {
        max_tail_loss_probes_ = 0;
    }
    if (config.HasClientSentConnectionOption(kTLPR, perspective_)) {
        enable_half_rtt_tail_loss_probe_ = true;
    }
    if (config.HasClientSentConnectionOption(kNRTO, perspective_)) {
        use_new_rto_ = true;
    }
    if (config.HasReceivedConnectionOptions() && ContainsQuicTag(config.ReceivedConnectionOptions(), kTIME)) {
        loss_algorithm_.reset(new GeneralLossAlgorithm(kTime));
    }
    if (config.HasReceivedConnectionOptions() && ContainsQuicTag(config.ReceivedConnectionOptions(), kATIM)) {
        loss_algorithm_.reset(new GeneralLossAlgorithm(kAdaptiveTime));
    }
    if (FLAGS_quic_loss_recovery_use_largest_acked && config.HasClientSentConnectionOption(kUNDO, perspective_)) {
        undo_pending_retransmits_ = true;
    }
    if (!FLAGS_quic_ignore_srbf && config.HasReceivedSocketReceiveBuffer()) {
        receive_buffer_bytes_ = max(kMinSocketReceiveBuffer,
            static_cast<QuicByteCount>(config.ReceivedSocketReceiveBuffer()));
        QuicByteCount max_cwnd_bytes = static_cast<QuicByteCount>(
            receive_buffer_bytes_ * kConservativeReceiveBufferFraction);
        send_algorithm_->SetMaxCongestionWindow(max_cwnd_bytes);
    }
    send_algorithm_->SetFromConfig(config, perspective_);

    if (network_change_visitor_ != nullptr) {
        network_change_visitor_->OnCongestionChange();
    }
}

void QuicSentPacketManager::ResumeConnectionState(
    const CachedNetworkParameters& cached_network_params,
    bool max_bandwidth_resumption)
{
    if (cached_network_params.has_min_rtt_ms()) {
        uint32_t initial_rtt_us = kNumMicrosPerMilli * cached_network_params.min_rtt_ms();
        rtt_stats_.set_initial_rtt_us(
            max(kMinInitialRoundTripTimeUs,
                min(kMaxInitialRoundTripTimeUs, initial_rtt_us)));
    }
    send_algorithm_->ResumeConnectionState(cached_network_params,
        max_bandwidth_resumption);
}

void QuicSentPacketManager::SetNumOpenStreams(size_t num_streams)
{
    if (n_connection_simulation_) {
        // Ensure the number of connections is between 1 and 5.
        send_algorithm_->SetNumEmulatedConnections(
            min<size_t>(5, max<size_t>(1, num_streams)));
    }
}

void QuicSentPacketManager::SetMaxPacingRate(QuicBandwidth max_pacing_rate)
{
    if (using_pacing_) {
        static_cast<PacingSender*>(send_algorithm_.get())
            ->SetMaxPacingRate(max_pacing_rate);
    }
}

void QuicSentPacketManager::SetHandshakeConfirmed()
{
    handshake_confirmed_ = true;
}

void QuicSentPacketManager::OnIncomingAck(const QuicAckFrame& ack_frame,
    QuicTime ack_receive_time)
{
    DCHECK_LE(ack_frame.largest_observed, unacked_packets_.largest_sent_packet());
    QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight();
    UpdatePacketInformationReceivedByPeer(ack_frame);
    bool rtt_updated = MaybeUpdateRTT(ack_frame, ack_receive_time);
    DCHECK_GE(ack_frame.largest_observed, unacked_packets_.largest_observed());
    unacked_packets_.IncreaseLargestObserved(ack_frame.largest_observed);

    HandleAckForSentPackets(ack_frame);
    InvokeLossDetection(ack_receive_time);
    // Ignore losses in RTO mode.
    if (consecutive_rto_count_ > 0 && !use_new_rto_) {
        packets_lost_.clear();
    }
    MaybeInvokeCongestionEvent(rtt_updated, bytes_in_flight);
    unacked_packets_.RemoveObsoletePackets();

    sustained_bandwidth_recorder_.RecordEstimate(
        send_algorithm_->InRecovery(), send_algorithm_->InSlowStart(),
        send_algorithm_->BandwidthEstimate(), ack_receive_time, clock_->WallNow(),
        rtt_stats_.smoothed_rtt());

    // Anytime we are making forward progress and have a new RTT estimate, reset
    // the backoff counters.
    if (rtt_updated) {
        if (consecutive_rto_count_ > 0) {
            // If the ack acknowledges data sent prior to the RTO,
            // the RTO was spurious.
            if (ack_frame.largest_observed < first_rto_transmission_) {
                // Replace SRTT with latest_rtt and increase the variance to prevent
                // a spurious RTO from happening again.
                rtt_stats_.ExpireSmoothedMetrics();
            } else {
                if (!use_new_rto_) {
                    send_algorithm_->OnRetransmissionTimeout(true);
                }
            }
        }
        // Reset all retransmit counters any time a new packet is acked.
        consecutive_rto_count_ = 0;
        consecutive_tlp_count_ = 0;
        consecutive_crypto_retransmission_count_ = 0;
    }
    // TODO(ianswett): Consider replacing the pending_retransmissions_ with a
    // fast way to retrieve the next pending retransmission, if there are any.
    // A single packet number indicating all packets below that are lost should
    // be all the state that is necessary.
    while (undo_pending_retransmits_ && !pending_retransmissions_.empty() && pending_retransmissions_.front().first > largest_newly_acked_ && pending_retransmissions_.front().second == LOSS_RETRANSMISSION) {
        // Cancel any pending retransmissions larger than largest_newly_acked_.
        unacked_packets_.RestoreToInFlight(pending_retransmissions_.front().first);
        pending_retransmissions_.erase(pending_retransmissions_.begin());
    }

    if (debug_delegate_ != nullptr) {
        debug_delegate_->OnIncomingAck(ack_frame, ack_receive_time,
            unacked_packets_.largest_observed(),
            rtt_updated, GetLeastUnacked(path_id_));
    }
}

void QuicSentPacketManager::UpdatePacketInformationReceivedByPeer(
    const QuicAckFrame& ack_frame)
{
    if (ack_frame.packets.Empty()) {
        least_packet_awaited_by_peer_ = ack_frame.largest_observed + 1;
    } else {
        least_packet_awaited_by_peer_ = ack_frame.packets.Min();
    }
}

void QuicSentPacketManager::MaybeInvokeCongestionEvent(
    bool rtt_updated,
    QuicByteCount bytes_in_flight)
{
    if (!rtt_updated && packets_acked_.empty() && packets_lost_.empty()) {
        return;
    }
    send_algorithm_->OnCongestionEvent(rtt_updated, bytes_in_flight,
        packets_acked_, packets_lost_);
    packets_acked_.clear();
    packets_lost_.clear();
    if (network_change_visitor_ != nullptr) {
        network_change_visitor_->OnCongestionChange();
    }
}

void QuicSentPacketManager::HandleAckForSentPackets(
    const QuicAckFrame& ack_frame)
{
    // Go through the packets we have not received an ack for and see if this
    // incoming_ack shows they've been seen by the peer.
    QuicTime::Delta ack_delay_time = ack_frame.ack_delay_time;
    QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
    for (QuicUnackedPacketMap::iterator it = unacked_packets_.begin();
         it != unacked_packets_.end(); ++it, ++packet_number) {
        if (packet_number > ack_frame.largest_observed) {
            // These packets are still in flight.
            break;
        }

        if ((ack_frame.missing && ack_frame.packets.Contains(packet_number)) || (!ack_frame.missing && !ack_frame.packets.Contains(packet_number))) {
            // Packet is still missing.
            continue;
        }
        // Packet was acked, so remove it from our unacked packet list.
        DVLOG(1) << ENDPOINT << "Got an ack for packet " << packet_number;
        // If data is associated with the most recent transmission of this
        // packet, then inform the caller.
        if (it->in_flight) {
            packets_acked_.push_back(std::make_pair(packet_number, it->bytes_sent));
        } else if (FLAGS_quic_loss_recovery_use_largest_acked && !it->is_unackable) {
            largest_newly_acked_ = packet_number;
        }
        MarkPacketHandled(packet_number, &(*it), ack_delay_time);
    }
}

bool QuicSentPacketManager::HasRetransmittableFrames(
    QuicPathId,
    QuicPacketNumber packet_number) const
{
    return unacked_packets_.HasRetransmittableFrames(packet_number);
}

void QuicSentPacketManager::RetransmitUnackedPackets(
    TransmissionType retransmission_type)
{
    DCHECK(retransmission_type == ALL_UNACKED_RETRANSMISSION || retransmission_type == ALL_INITIAL_RETRANSMISSION);
    QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
    for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
         it != unacked_packets_.end(); ++it, ++packet_number) {
        if (!it->retransmittable_frames.empty() && (retransmission_type == ALL_UNACKED_RETRANSMISSION || it->encryption_level == ENCRYPTION_INITIAL)) {
            MarkForRetransmission(packet_number, retransmission_type);
        }
    }
}

void QuicSentPacketManager::NeuterUnencryptedPackets()
{
    QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
    for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
         it != unacked_packets_.end(); ++it, ++packet_number) {
        if (!it->retransmittable_frames.empty() && it->encryption_level == ENCRYPTION_NONE) {
            // Once you're forward secure, no unencrypted packets will be sent, crypto
            // or otherwise. Unencrypted packets are neutered and abandoned, to ensure
            // they are not retransmitted or considered lost from a congestion control
            // perspective.
            if (delegate_ != nullptr) {
                delegate_->OnUnencryptedPacketsNeutered(path_id_, packet_number);
            } else {
                pending_retransmissions_.erase(packet_number);
            }
            unacked_packets_.RemoveFromInFlight(packet_number);
            unacked_packets_.RemoveRetransmittability(packet_number);
        }
    }
}

void QuicSentPacketManager::MarkForRetransmission(
    QuicPacketNumber packet_number,
    TransmissionType transmission_type)
{
    const TransmissionInfo& transmission_info = unacked_packets_.GetTransmissionInfo(packet_number);
    QUIC_BUG_IF(transmission_info.retransmittable_frames.empty());
    // Both TLP and the new RTO leave the packets in flight and let the loss
    // detection decide if packets are lost.
    if (transmission_type != TLP_RETRANSMISSION && transmission_type != RTO_RETRANSMISSION) {
        unacked_packets_.RemoveFromInFlight(packet_number);
    }
    if (delegate_ != nullptr) {
        delegate_->OnRetransmissionMarked(path_id_, packet_number,
            transmission_type);
    } else {
        // TODO(ianswett): Currently the RTO can fire while there are pending NACK
        // retransmissions for the same data, which is not ideal.
        if (ContainsKey(pending_retransmissions_, packet_number)) {
            return;
        }

        pending_retransmissions_[packet_number] = transmission_type;
    }
}

void QuicSentPacketManager::RecordOneSpuriousRetransmission(
    const TransmissionInfo& info)
{
    stats_->bytes_spuriously_retransmitted += info.bytes_sent;
    ++stats_->packets_spuriously_retransmitted;
    if (debug_delegate_ != nullptr) {
        debug_delegate_->OnSpuriousPacketRetransmission(info.transmission_type,
            info.bytes_sent);
    }
}

void QuicSentPacketManager::RecordSpuriousRetransmissions(
    const TransmissionInfo& info,
    QuicPacketNumber acked_packet_number)
{
    QuicPacketNumber retransmission = info.retransmission;
    while (retransmission != 0) {
        const TransmissionInfo& retransmit_info = unacked_packets_.GetTransmissionInfo(retransmission);
        retransmission = retransmit_info.retransmission;
        RecordOneSpuriousRetransmission(retransmit_info);
    }
    // Only inform the loss detection of spurious retransmits it caused.
    if (unacked_packets_.GetTransmissionInfo(info.retransmission)
            .transmission_type
        == LOSS_RETRANSMISSION) {
        loss_algorithm_->SpuriousRetransmitDetected(
            unacked_packets_, clock_->Now(), rtt_stats_, info.retransmission);
    }
}

bool QuicSentPacketManager::HasPendingRetransmissions() const
{
    return !pending_retransmissions_.empty();
}

PendingRetransmission QuicSentPacketManager::NextPendingRetransmission()
{
    QUIC_BUG_IF(pending_retransmissions_.empty())
        << "Unexpected call to PendingRetransmissions() with empty pending "
        << "retransmission list. Corrupted memory usage imminent.";
    QuicPacketNumber packet_number = pending_retransmissions_.begin()->first;
    TransmissionType transmission_type = pending_retransmissions_.begin()->second;
    if (unacked_packets_.HasPendingCryptoPackets()) {
        // Ensure crypto packets are retransmitted before other packets.
        for (const auto& pair : pending_retransmissions_) {
            if (HasCryptoHandshake(
                    unacked_packets_.GetTransmissionInfo(pair.first))) {
                packet_number = pair.first;
                transmission_type = pair.second;
                break;
            }
        }
    }
    DCHECK(unacked_packets_.IsUnacked(packet_number)) << packet_number;
    const TransmissionInfo& transmission_info = unacked_packets_.GetTransmissionInfo(packet_number);
    DCHECK(!transmission_info.retransmittable_frames.empty());

    return PendingRetransmission(path_id_, packet_number, transmission_type,
        transmission_info.retransmittable_frames,
        transmission_info.has_crypto_handshake,
        transmission_info.num_padding_bytes,
        transmission_info.encryption_level,
        transmission_info.packet_number_length);
}

QuicPacketNumber QuicSentPacketManager::GetNewestRetransmission(
    QuicPacketNumber packet_number,
    const TransmissionInfo& transmission_info) const
{
    QuicPacketNumber retransmission = transmission_info.retransmission;
    while (retransmission != 0) {
        packet_number = retransmission;
        retransmission = unacked_packets_.GetTransmissionInfo(retransmission).retransmission;
    }
    return packet_number;
}

void QuicSentPacketManager::MarkPacketNotRetransmittable(
    QuicPacketNumber packet_number,
    QuicTime::Delta ack_delay_time)
{
    if (!unacked_packets_.IsUnacked(packet_number)) {
        return;
    }

    const TransmissionInfo& transmission_info = unacked_packets_.GetTransmissionInfo(packet_number);
    QuicPacketNumber newest_transmission = GetNewestRetransmission(packet_number, transmission_info);
    // We do not need to retransmit this packet anymore.
    if (delegate_ != nullptr) {
        delegate_->OnPacketMarkedNotRetransmittable(path_id_, newest_transmission,
            ack_delay_time);
    } else {
        pending_retransmissions_.erase(newest_transmission);
    }

    unacked_packets_.NotifyAndClearListeners(newest_transmission, ack_delay_time);
    unacked_packets_.RemoveRetransmittability(packet_number);
}

void QuicSentPacketManager::MarkPacketHandled(QuicPacketNumber packet_number,
    TransmissionInfo* info,
    QuicTime::Delta ack_delay_time)
{
    QuicPacketNumber newest_transmission = GetNewestRetransmission(packet_number, *info);
    // Remove the most recent packet, if it is pending retransmission.
    if (delegate_ != nullptr) {
        delegate_->OnPacketMarkedHandled(path_id_, newest_transmission,
            ack_delay_time);
    } else {
        pending_retransmissions_.erase(newest_transmission);
    }

    // The AckListener needs to be notified about the most recent
    // transmission, since that's the one only one it tracks.
    if (newest_transmission == packet_number) {
        unacked_packets_.NotifyAndClearListeners(&info->ack_listeners,
            ack_delay_time);
    } else {
        unacked_packets_.NotifyAndClearListeners(newest_transmission,
            ack_delay_time);
        RecordSpuriousRetransmissions(*info, packet_number);
        // Remove the most recent packet from flight if it's a crypto handshake
        // packet, since they won't be acked now that one has been processed.
        // Other crypto handshake packets won't be in flight, only the newest
        // transmission of a crypto packet is in flight at once.
        // TODO(ianswett): Instead of handling all crypto packets special,
        // only handle nullptr encrypted packets in a special way.
        const TransmissionInfo& newest_transmission_info = unacked_packets_.GetTransmissionInfo(newest_transmission);
        if (HasCryptoHandshake(newest_transmission_info)) {
            unacked_packets_.RemoveFromInFlight(newest_transmission);
        }
    }

    if (FLAGS_quic_no_mtu_discovery_ack_listener && network_change_visitor_ != nullptr && info->bytes_sent > largest_mtu_acked_) {
        largest_mtu_acked_ = info->bytes_sent;
        network_change_visitor_->OnPathMtuIncreased(largest_mtu_acked_);
    }
    unacked_packets_.RemoveFromInFlight(info);
    unacked_packets_.RemoveRetransmittability(info);
    if (FLAGS_quic_loss_recovery_use_largest_acked) {
        info->is_unackable = true;
    }
}

bool QuicSentPacketManager::IsUnacked(QuicPathId,
    QuicPacketNumber packet_number) const
{
    return unacked_packets_.IsUnacked(packet_number);
}

bool QuicSentPacketManager::HasUnackedPackets() const
{
    return unacked_packets_.HasUnackedPackets();
}

QuicPacketNumber QuicSentPacketManager::GetLeastUnacked(QuicPathId) const
{
    return unacked_packets_.GetLeastUnacked();
}

bool QuicSentPacketManager::OnPacketSent(
    SerializedPacket* serialized_packet,
    QuicPathId /*original_path_id*/,
    QuicPacketNumber original_packet_number,
    QuicTime sent_time,
    TransmissionType transmission_type,
    HasRetransmittableData has_retransmittable_data)
{
    QuicPacketNumber packet_number = serialized_packet->packet_number;
    DCHECK_LT(0u, packet_number);
    DCHECK(!unacked_packets_.IsUnacked(packet_number));
    QUIC_BUG_IF(serialized_packet->encrypted_length == 0)
        << "Cannot send empty packets.";

    if (delegate_ == nullptr && original_packet_number != 0) {
        if (!pending_retransmissions_.erase(original_packet_number) && !FLAGS_quic_always_write_queued_retransmissions) {
            QUIC_BUG << "Expected packet number to be in "
                     << "pending_retransmissions_.  packet_number: "
                     << original_packet_number;
        }
    }

    if (pending_timer_transmission_count_ > 0) {
        --pending_timer_transmission_count_;
    }

    // TODO(ianswett): Remove sent_time, because it's unused.
    const bool in_flight = send_algorithm_->OnPacketSent(
        sent_time, unacked_packets_.bytes_in_flight(), packet_number,
        serialized_packet->encrypted_length, has_retransmittable_data);

    unacked_packets_.AddSentPacket(serialized_packet, original_packet_number,
        transmission_type, sent_time, in_flight);
    // Reset the retransmission timer anytime a pending packet is sent.
    return in_flight;
}

void QuicSentPacketManager::OnRetransmissionTimeout()
{
    DCHECK(unacked_packets_.HasInFlightPackets());
    DCHECK_EQ(0u, pending_timer_transmission_count_);
    // Handshake retransmission, timer based loss detection, TLP, and RTO are
    // implemented with a single alarm. The handshake alarm is set when the
    // handshake has not completed, the loss alarm is set when the loss detection
    // algorithm says to, and the TLP and  RTO alarms are set after that.
    // The TLP alarm is always set to run for under an RTO.
    switch (GetRetransmissionMode()) {
    case HANDSHAKE_MODE:
        ++stats_->crypto_retransmit_count;
        RetransmitCryptoPackets();
        return;
    case LOSS_MODE: {
        ++stats_->loss_timeout_count;
        QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight();
        InvokeLossDetection(clock_->Now());
        MaybeInvokeCongestionEvent(false, bytes_in_flight);
        return;
    }
    case TLP_MODE:
        // If no tail loss probe can be sent, because there are no retransmittable
        // packets, execute a conventional RTO to abandon old packets.
        ++stats_->tlp_count;
        ++consecutive_tlp_count_;
        pending_timer_transmission_count_ = 1;
        // TLPs prefer sending new data instead of retransmitting data, so
        // give the connection a chance to write before completing the TLP.
        return;
    case RTO_MODE:
        ++stats_->rto_count;
        RetransmitRtoPackets();
        if (network_change_visitor_ != nullptr && consecutive_rto_count_ == kMinTimeoutsBeforePathDegrading) {
            network_change_visitor_->OnPathDegrading();
        }
        return;
    }
}

void QuicSentPacketManager::RetransmitCryptoPackets()
{
    DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode());
    ++consecutive_crypto_retransmission_count_;
    bool packet_retransmitted = false;
    QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
    for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
         it != unacked_packets_.end(); ++it, ++packet_number) {
        // Only retransmit frames which are in flight, and therefore have been sent.
        if (!it->in_flight || it->retransmittable_frames.empty() || !it->has_crypto_handshake) {
            continue;
        }
        packet_retransmitted = true;
        MarkForRetransmission(packet_number, HANDSHAKE_RETRANSMISSION);
        ++pending_timer_transmission_count_;
    }
    DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
}

bool QuicSentPacketManager::MaybeRetransmitTailLossProbe()
{
    if (pending_timer_transmission_count_ == 0) {
        return false;
    }
    QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
    for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
         it != unacked_packets_.end(); ++it, ++packet_number) {
        // Only retransmit frames which are in flight, and therefore have been sent.
        if (!it->in_flight || it->retransmittable_frames.empty()) {
            continue;
        }
        if (!handshake_confirmed_) {
            DCHECK(!it->has_crypto_handshake);
        }
        MarkForRetransmission(packet_number, TLP_RETRANSMISSION);
        return true;
    }
    DLOG(ERROR)
        << "No retransmittable packets, so RetransmitOldestPacket failed.";
    return false;
}

void QuicSentPacketManager::RetransmitRtoPackets()
{
    QUIC_BUG_IF(pending_timer_transmission_count_ > 0)
        << "Retransmissions already queued:" << pending_timer_transmission_count_;
    // Mark two packets for retransmission.
    QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
    for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
         it != unacked_packets_.end(); ++it, ++packet_number) {
        if (!it->retransmittable_frames.empty() && pending_timer_transmission_count_ < kMaxRetransmissionsOnTimeout) {
            MarkForRetransmission(packet_number, RTO_RETRANSMISSION);
            ++pending_timer_transmission_count_;
        }
        // Abandon non-retransmittable data that's in flight to ensure it doesn't
        // fill up the congestion window.
        const bool has_retransmissions = it->retransmission != 0;
        if (it->retransmittable_frames.empty() && it->in_flight && !has_retransmissions) {
            // Log only for non-retransmittable data.
            // Retransmittable data is marked as lost during loss detection, and will
            // be logged later.
            unacked_packets_.RemoveFromInFlight(packet_number);
            if (debug_delegate_ != nullptr) {
                debug_delegate_->OnPacketLoss(packet_number, RTO_RETRANSMISSION,
                    clock_->Now());
            }
        }
    }
    if (pending_timer_transmission_count_ > 0) {
        if (consecutive_rto_count_ == 0) {
            first_rto_transmission_ = unacked_packets_.largest_sent_packet() + 1;
        }
        ++consecutive_rto_count_;
    }
}

QuicSentPacketManager::RetransmissionTimeoutMode
QuicSentPacketManager::GetRetransmissionMode() const
{
    DCHECK(unacked_packets_.HasInFlightPackets());
    if (!handshake_confirmed_ && unacked_packets_.HasPendingCryptoPackets()) {
        return HANDSHAKE_MODE;
    }
    if (loss_algorithm_->GetLossTimeout() != QuicTime::Zero()) {
        return LOSS_MODE;
    }
    if (consecutive_tlp_count_ < max_tail_loss_probes_) {
        if (unacked_packets_.HasUnackedRetransmittableFrames()) {
            return TLP_MODE;
        }
    }
    return RTO_MODE;
}

void QuicSentPacketManager::InvokeLossDetection(QuicTime time)
{
    if (FLAGS_quic_loss_recovery_use_largest_acked && !packets_acked_.empty()) {
        DCHECK_LE(packets_acked_.front().first, packets_acked_.back().first);
        largest_newly_acked_ = packets_acked_.back().first;
    }
    loss_algorithm_->DetectLosses(unacked_packets_, time, rtt_stats_,
        largest_newly_acked_, &packets_lost_);
    for (const pair<QuicPacketNumber, QuicByteCount>& pair : packets_lost_) {
        ++stats_->packets_lost;
        if (debug_delegate_ != nullptr) {
            debug_delegate_->OnPacketLoss(pair.first, LOSS_RETRANSMISSION, time);
        }

        // TODO(ianswett): This could be optimized.
        if (unacked_packets_.HasRetransmittableFrames(pair.first)) {
            MarkForRetransmission(pair.first, LOSS_RETRANSMISSION);
        } else {
            // Since we will not retransmit this, we need to remove it from
            // unacked_packets_.   This is either the current transmission of
            // a packet whose previous transmission has been acked or a packet that
            // has been TLP retransmitted.
            unacked_packets_.RemoveFromInFlight(pair.first);
        }
    }
}

bool QuicSentPacketManager::MaybeUpdateRTT(const QuicAckFrame& ack_frame,
    QuicTime ack_receive_time)
{
    // We rely on ack_delay_time to compute an RTT estimate, so we
    // only update rtt when the largest observed gets acked.
    // NOTE: If ack is a truncated ack, then the largest observed is in fact
    // unacked, and may cause an RTT sample to be taken.
    if (!unacked_packets_.IsUnacked(ack_frame.largest_observed)) {
        return false;
    }
    // We calculate the RTT based on the highest ACKed packet number, the lower
    // packet numbers will include the ACK aggregation delay.
    const TransmissionInfo& transmission_info = unacked_packets_.GetTransmissionInfo(ack_frame.largest_observed);
    // Ensure the packet has a valid sent time.
    if (transmission_info.sent_time == QuicTime::Zero()) {
        QUIC_BUG << "Acked packet has zero sent time, largest_observed:"
                 << ack_frame.largest_observed;
        return false;
    }

    QuicTime::Delta send_delta = ack_receive_time.Subtract(transmission_info.sent_time);
    const int kMaxSendDeltaSeconds = 30;
    if (FLAGS_quic_socket_walltimestamps && send_delta.ToSeconds() > kMaxSendDeltaSeconds) {
        // send_delta can be very high if local clock is changed mid-connection.
        LOG(WARNING) << "Excessive send delta: " << send_delta.ToSeconds()
                     << ", setting to: " << kMaxSendDeltaSeconds;
        send_delta = QuicTime::Delta::FromSeconds(kMaxSendDeltaSeconds);
    }
    rtt_stats_.UpdateRtt(send_delta, ack_frame.ack_delay_time, ack_receive_time);

    return true;
}

QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
    QuicTime now,
    HasRetransmittableData retransmittable,
    QuicPathId* path_id)
{
    QuicTime::Delta delay = QuicTime::Delta::Infinite();
    // The TLP logic is entirely contained within QuicSentPacketManager, so the
    // send algorithm does not need to be consulted.
    if (pending_timer_transmission_count_ > 0) {
        delay = QuicTime::Delta::Zero();
    } else {
        delay = send_algorithm_->TimeUntilSend(now, unacked_packets_.bytes_in_flight());
    }
    if (!delay.IsInfinite()) {
        *path_id = path_id_;
    }
    return delay;
}

const QuicTime QuicSentPacketManager::GetRetransmissionTime() const
{
    // Don't set the timer if there are no packets in flight or we've already
    // queued a tlp transmission and it hasn't been sent yet.
    if (!unacked_packets_.HasInFlightPackets() || pending_timer_transmission_count_ > 0) {
        return QuicTime::Zero();
    }
    switch (GetRetransmissionMode()) {
    case HANDSHAKE_MODE:
        return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
    case LOSS_MODE:
        return loss_algorithm_->GetLossTimeout();
    case TLP_MODE: {
        // TODO(ianswett): When CWND is available, it would be preferable to
        // set the timer based on the earliest retransmittable packet.
        // Base the updated timer on the send time of the last packet.
        const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
        const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay());
        // Ensure the TLP timer never gets set to a time in the past.
        return QuicTime::Max(clock_->ApproximateNow(), tlp_time);
    }
    case RTO_MODE: {
        // The RTO is based on the first outstanding packet.
        const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
        QuicTime rto_time = sent_time.Add(GetRetransmissionDelay());
        // Wait for TLP packets to be acked before an RTO fires.
        QuicTime tlp_time = unacked_packets_.GetLastPacketSentTime().Add(GetTailLossProbeDelay());
        return QuicTime::Max(tlp_time, rto_time);
    }
    }
    DCHECK(false);
    return QuicTime::Zero();
}

const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay()
    const
{
    // This is equivalent to the TailLossProbeDelay, but slightly more aggressive
    // because crypto handshake messages don't incur a delayed ack time.
    QuicTime::Delta srtt = rtt_stats_.smoothed_rtt();
    if (srtt.IsZero()) {
        srtt = QuicTime::Delta::FromMicroseconds(rtt_stats_.initial_rtt_us());
    }
    int64_t delay_ms = max(kMinHandshakeTimeoutMs,
        static_cast<int64_t>(1.5 * srtt.ToMilliseconds()));
    return QuicTime::Delta::FromMilliseconds(
        delay_ms << consecutive_crypto_retransmission_count_);
}

const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const
{
    QuicTime::Delta srtt = rtt_stats_.smoothed_rtt();
    if (srtt.IsZero()) {
        srtt = QuicTime::Delta::FromMicroseconds(rtt_stats_.initial_rtt_us());
    }
    if (enable_half_rtt_tail_loss_probe_ && consecutive_tlp_count_ == 0u) {
        return QuicTime::Delta::FromMilliseconds(
            max(kMinTailLossProbeTimeoutMs,
                static_cast<int64_t>(0.5 * srtt.ToMilliseconds())));
    }
    if (!unacked_packets_.HasMultipleInFlightPackets()) {
        return QuicTime::Delta::Max(
            srtt.Multiply(2),
            srtt.Multiply(1.5).Add(
                QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs / 2)));
    }
    return QuicTime::Delta::FromMilliseconds(
        max(kMinTailLossProbeTimeoutMs,
            static_cast<int64_t>(2 * srtt.ToMilliseconds())));
}

const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const
{
    QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
    if (retransmission_delay.IsZero()) {
        // We are in the initial state, use default timeout values.
        retransmission_delay = QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
    } else if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
        retransmission_delay = QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
    }

    // Calculate exponential back off.
    retransmission_delay = retransmission_delay.Multiply(
        1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions));

    if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
        return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
    }
    return retransmission_delay;
}

const RttStats* QuicSentPacketManager::GetRttStats() const
{
    return &rtt_stats_;
}

QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const
{
    // TODO(ianswett): Remove BandwidthEstimate from SendAlgorithmInterface
    // and implement the logic here.
    return send_algorithm_->BandwidthEstimate();
}

const QuicSustainedBandwidthRecorder&
QuicSentPacketManager::SustainedBandwidthRecorder() const
{
    return sustained_bandwidth_recorder_;
}

QuicPacketCount QuicSentPacketManager::EstimateMaxPacketsInFlight(
    QuicByteCount max_packet_length) const
{
    return send_algorithm_->GetCongestionWindow() / max_packet_length;
}

QuicPacketCount QuicSentPacketManager::GetCongestionWindowInTcpMss() const
{
    return send_algorithm_->GetCongestionWindow() / kDefaultTCPMSS;
}

QuicByteCount QuicSentPacketManager::GetCongestionWindowInBytes() const
{
    return send_algorithm_->GetCongestionWindow();
}

QuicPacketCount QuicSentPacketManager::GetSlowStartThresholdInTcpMss() const
{
    return send_algorithm_->GetSlowStartThreshold() / kDefaultTCPMSS;
}

void QuicSentPacketManager::CancelRetransmissionsForStream(
    QuicStreamId stream_id)
{
    unacked_packets_.CancelRetransmissionsForStream(stream_id);
    if (delegate_ != nullptr) {
        return;
    }
    PendingRetransmissionMap::iterator it = pending_retransmissions_.begin();
    while (it != pending_retransmissions_.end()) {
        if (HasRetransmittableFrames(path_id_, it->first)) {
            ++it;
            continue;
        }
        it = pending_retransmissions_.erase(it);
    }
}

void QuicSentPacketManager::EnablePacing()
{
    // TODO(ianswett): Replace with a method which wraps the send algorithm in a
    // pacer every time a new algorithm is set.
    if (using_pacing_) {
        return;
    }

    // Set up a pacing sender with a 1 millisecond alarm granularity, the same as
    // the default granularity of the Linux kernel's FQ qdisc.
    using_pacing_ = true;
    send_algorithm_.reset(new PacingSender(send_algorithm_.release(),
        QuicTime::Delta::FromMilliseconds(1),
        kInitialUnpacedBurst));
}

void QuicSentPacketManager::OnConnectionMigration(QuicPathId,
    PeerAddressChangeType type)
{
    if (type == PORT_CHANGE || type == IPV4_SUBNET_CHANGE) {
        // Rtt and cwnd do not need to be reset when the peer address change is
        // considered to be caused by NATs.
        return;
    }
    consecutive_rto_count_ = 0;
    consecutive_tlp_count_ = 0;
    rtt_stats_.OnConnectionMigration();
    send_algorithm_->OnConnectionMigration();
}

bool QuicSentPacketManager::IsHandshakeConfirmed() const
{
    return handshake_confirmed_;
}

void QuicSentPacketManager::SetDebugDelegate(DebugDelegate* debug_delegate)
{
    debug_delegate_ = debug_delegate;
}

QuicPacketNumber QuicSentPacketManager::GetLargestObserved(QuicPathId) const
{
    return unacked_packets_.largest_observed();
}

QuicPacketNumber QuicSentPacketManager::GetLargestSentPacket(QuicPathId) const
{
    return unacked_packets_.largest_sent_packet();
}

QuicPacketNumber QuicSentPacketManager::GetLeastPacketAwaitedByPeer(
    QuicPathId) const
{
    return least_packet_awaited_by_peer_;
}

void QuicSentPacketManager::SetNetworkChangeVisitor(
    NetworkChangeVisitor* visitor)
{
    DCHECK(!network_change_visitor_);
    DCHECK(visitor);
    network_change_visitor_ = visitor;
}

bool QuicSentPacketManager::InSlowStart() const
{
    return send_algorithm_->InSlowStart();
}

size_t QuicSentPacketManager::GetConsecutiveRtoCount() const
{
    return consecutive_rto_count_;
}

size_t QuicSentPacketManager::GetConsecutiveTlpCount() const
{
    return consecutive_tlp_count_;
}

TransmissionInfo* QuicSentPacketManager::GetMutableTransmissionInfo(
    QuicPacketNumber packet_number)
{
    return unacked_packets_.GetMutableTransmissionInfo(packet_number);
}

void QuicSentPacketManager::RemoveObsoletePackets()
{
    unacked_packets_.RemoveObsoletePackets();
}

} // namespace net
